package com.graph6;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;


public class GroupTest2_fix {

	/**
	 * <code>
	 * 	LIBRARY          LIBRARY DEPENDENCIES
	=======          ====================
	des_system_lib   std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
	dw01             ieee dw01 dware gtech
	dw02             ieee dw02 dware
	dw03             std synopsys dware dw03 dw02 dw01 ieee gtech
	dw04             dw04 ieee dw01 dware gtech
	dw05             dw05 ieee dware
	dw06             dw06 ieee dware
	dw07             ieee dware
	dware            ieee dware
	gtech            ieee gtech
	ramlib           std ieee
	std_cell_lib     ieee std_cell_lib
	synopsys
	 * </code>
	 * 
	 */

	public static void main(String[] args) {

		int[][] edges = new int[][] { //
				{ 2, 0 }, { 2, 14 }, { 2, 13 }, { 2, 4 }, { 2, 3 }, { 2, 12 }, { 2, 1 }, //
				{ 3, 1 }, { 3, 10 }, { 3, 11 }, //
				{ 4, 1 }, { 4, 10 }, //
				{ 5, 0 }, { 5, 14 }, { 5, 10 }, { 5, 4 }, { 5, 3 }, { 5, 1 }, { 5, 11 }, //
				{ 6, 1 }, { 6, 3 }, { 6, 10 }, { 6, 11 }, //
				{ 7, 1 }, { 7, 10 }, //
				{ 8, 1 }, { 8, 10 }, //
				{ 9, 1 }, { 9, 10 }, //
				{ 10, 1 }, //
				{ 11, 1 }, //
				{ 12, 0 }, { 12, 1 }, //
				{ 13, 1 }, //
				{ 15, 16 },{ 15, 20 }, //
				{ 17, 18 }, //
				{ 19, 20 }, //
				};

		Graph2 g = new Graph2(21, edges);
		List<Integer> sort = g.topoSort2();
		System.out.println("sort:" + sort);
//		组之间并行==，组内串行||
		List<Tx> txs = new ArrayList<Tx>();
		for (int[] edge : edges) {
			txs.add(new Tx(edge[0], edge[1]));
		}
		HashMap<Integer, List<Tx>> map = new HashMap<Integer, List<Tx>>();

		int group = 0;
		while (!txs.isEmpty()) {// 还有数据
			Integer vertex = sort.get(0);
			Set<Integer> set = new HashSet<Integer>();
			set.add(vertex);
			Iterator<Tx> iterator = txs.iterator();
			List<Tx> txadd = new ArrayList<Tx>();

//			for (Integer ss : sort) {

				while (iterator.hasNext()) {
					Tx tx = iterator.next();

					if (set.contains(tx.getFrom()) || set.contains(tx.getTo())) {
						set.add(tx.getFrom());
						set.add(tx.getTo());
						txadd.add(tx);
						iterator.remove();
					}

				}

//			}
			map.put(group, txadd);
			group++;
		}
		map.forEach((key, value) -> {
			System.out.println("group:" + key);
			for (Tx tx : value) {
				System.out.println("\t" + tx);
			}
		});

	}

}

class Graph2 {
	boolean[][] adjacency;
	int numVertices;

	public Graph2(int num, int[][] edges) {
		numVertices = num;
		adjacency = new boolean[numVertices][numVertices];

		for (int[] edge : edges)
			adjacency[edge[0]][edge[1]] = true; // 坐标上设置点
	}

	List<Integer> topoSort2() {
		List<Integer> result = new ArrayList<>();
		List<Integer> todo = new LinkedList<>();

		for (int i = 0; i < numVertices; i++)
			todo.add(i);

		try {
			outer: while (!todo.isEmpty()) {// 还有数据
				for (Integer r : todo) {
					if (!hasDependency(r, todo)) {// 没有依赖的元素移出
						todo.remove(r);
						result.add(r);
						continue outer;
					}
				}
				throw new Exception("Graph has cycles");
			}
		} catch (Exception e) {
			System.out.println(e);
			return null;
		}
		return result;
	}

	boolean hasDependency(Integer r, List<Integer> todo) {
		for (Integer c : todo) {
			if (adjacency[r][c]) {
				return true;
			}
		}
		return false;
	}
}